Search Results

Documents authored by Scheideler, Christian

Document
Complete Volume
DOI: 10.4230/LIPIcs.DISC.2022
LIPIcs, Volume 246, DISC 2022, Complete Volume

Authors: Christian Scheideler

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
LIPIcs, Volume 246, DISC 2022, Complete Volume
Cite as

36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 1-790, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{scheideler:LIPIcs.DISC.2022,
  title =	{{LIPIcs, Volume 246, DISC 2022, Complete Volume}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{1--790},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022},
  URN =		{urn:nbn:de:0030-drops-171908},
  doi =		{10.4230/LIPIcs.DISC.2022},
  annote =	{Keywords: LIPIcs, Volume 246, DISC 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.DISC.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christian Scheideler

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{scheideler:LIPIcs.DISC.2022.0,
  author =	{Scheideler, Christian},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.0},
  URN =		{urn:nbn:de:0030-drops-171917},
  doi =		{10.4230/LIPIcs.DISC.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.8
The Structural Power of Reconfigurable Circuits in the Amoebot Model

Authors: Andreas Padalkin, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by so-called circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.
Cite as

Andreas Padalkin, Christian Scheideler, and Daniel Warner. The Structural Power of Reconfigurable Circuits in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{padalkin_et_al:LIPIcs.DNA.28.8,
  author =	{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel},
  title =	{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.8},
  URN =		{urn:nbn:de:0030-drops-167935},
  doi =		{10.4230/LIPIcs.DNA.28.8},
  annote =	{Keywords: progammable matter, amoebot model, reconfigurable circuits, spanning tree, symmetry detection}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.9
Fault-Tolerant Shape Formation in the Amoebot Model

Authors: Irina Kostitsyna, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
The amoebot model is a distributed computing model of programmable matter. It envisions programmable matter as a collection of computational units called amoebots or particles that utilize local interactions to achieve tasks of coordination, movement and conformation. In the geometric amoebot model the particles operate on a hexagonal tessellation of the plane. Within this model, numerous problems such as leader election, shape formation or object coating have been studied. One area that has not received much attention so far, but is highly relevant for a practical implementation of programmable matter, is fault tolerance. The existing literature on that aspect allows particles to crash but assumes that crashed particles do not recover. We proposed a new model [Kostitsyna et al., 2022] in which a crash causes the memory of a particle to be reset and a crashed particle can detect that it has crashed and try to recover using its local information and communication capabilities. We present an algorithm that solves the hexagon shape formation problem in our model if a finite number of crashes occur and a designated leader particle does not fail. At the heart of our solution lies a fault-tolerant implementation of the spanning forest primitive, which, since other algorithms in the amoebot model also make use of it, is also of general interest.
Cite as

Irina Kostitsyna, Christian Scheideler, and Daniel Warner. Fault-Tolerant Shape Formation in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DNA.28.9,
  author =	{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
  title =	{{Fault-Tolerant Shape Formation in the Amoebot Model}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.9},
  URN =		{urn:nbn:de:0030-drops-167949},
  doi =		{10.4230/LIPIcs.DNA.28.9},
  annote =	{Keywords: programmable matter, amoebot model, fault tolerance, shape formation}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.12
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Mutual exclusion is a classical problem in distributed computing that provides isolation among concurrent action executions that may require access to the same shared resources. Inspired by algorithmic research on distributed systems of weakly capable entities whose connections change over time, we address the local mutual exclusion problem that tasks each node with acquiring exclusive locks for itself and the maximal subset of its "persistent" neighbors that remain connected to it over the time interval of the lock request. Using the established time-varying graphs model to capture adversarial topological changes, we propose and rigorously analyze a local mutual exclusion algorithm for nodes that are anonymous and communicate via asynchronous message passing. The algorithm satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. It requires 𝒪(Δ) memory per node and messages of size Θ(1), where Δ is the maximum number of connections per node. We conclude by describing how our algorithm can implement the pairwise interactions assumed by population protocols and the concurrency control operations assumed by the canonical amoebot model, demonstrating its utility in both passively and actively dynamic distributed systems.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.SAND.2022.12,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.12},
  URN =		{urn:nbn:de:0030-drops-159545},
  doi =		{10.4230/LIPIcs.SAND.2022.12},
  annote =	{Keywords: Mutual exclusion, dynamic networks, message passing, concurrency}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2022.23
Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model

Authors: Irina Kostitsyna, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
The amoebot model is a distributed computing model of programmable matter. It envisions programmable matter as a collection of computational units called amoebots or particles that utilize local interactions to achieve tasks of coordination, movement and conformation. In the geometric amoebot model the particles operate on a hexagonal tessellation of the plane. Within this model, numerous problems such as leader election, shape formation or object coating have been studied. One area that has not received much attention so far, but is highly relevant for a practical implementation of programmable matter, is fault tolerance. The existing literature on that aspect allows particles to crash but assumes that crashed particles do not recover. We propose a new model in which a crash causes the memory of a particle to be reset and a crashed particle can detect that it has crashed and try to recover using its local information and communication capabilities. We propose an algorithm that solves the hexagon shape formation problem in our model if a finite number of crashes occur and a designated leader particle does not fail. At the heart of our solution lies a fault-tolerant implementation of the spanning forest primitive, which, since other algorithms in the amoebot model also make use of it, is also of general interest.
Cite as

Irina Kostitsyna, Christian Scheideler, and Daniel Warner. Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 23:1-23:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SAND.2022.23,
  author =	{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
  title =	{{Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{23:1--23:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.23},
  URN =		{urn:nbn:de:0030-drops-159656},
  doi =		{10.4230/LIPIcs.SAND.2022.23},
  annote =	{Keywords: Programmable matter, Geometric amoebot model, Fault tolerance, Shape formation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.11
Near-Shortest Path Routing in Hybrid Communication Networks

Authors: Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.
Cite as

Sam Coy, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. Near-Shortest Path Routing in Hybrid Communication Networks. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coy_et_al:LIPIcs.OPODIS.2021.11,
  author =	{Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn},
  title =	{{Near-Shortest Path Routing in Hybrid Communication Networks}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.11},
  URN =		{urn:nbn:de:0030-drops-157863},
  doi =		{10.4230/LIPIcs.OPODIS.2021.11},
  annote =	{Keywords: Hybrid networks, overlay networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.20
The Canonical Amoebot Model: Algorithms and Concurrency Control

Authors: Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
Cite as

Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The Canonical Amoebot Model: Algorithms and Concurrency Control. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{daymude_et_al:LIPIcs.DISC.2021.20,
  author =	{Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
  title =	{{The Canonical Amoebot Model: Algorithms and Concurrency Control}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.20},
  URN =		{urn:nbn:de:0030-drops-148227},
  doi =		{10.4230/LIPIcs.DISC.2021.20},
  annote =	{Keywords: Programmable matter, self-organization, distributed algorithms, concurrency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.31
Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs

Authors: Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
We consider the problem of computing shortest paths in hybrid networks, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a local and a global mode. Specifically, the local edges model a fixed communication network in which O(1) messages of size O(log n) can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most O(log n) messages over global edges, which restricts the nodes to use these edges only very sparsely. We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in sparse graphs. Specifically, we present exact O(log n) time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and 3-approximations for graphs that have at most n + O(n^{1/3}) edges and arboricity O(log n). For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.
Cite as

Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.OPODIS.2020.31,
  author =	{Feldmann, Michael and Hinnenthal, Kristian and Scheideler, Christian},
  title =	{{Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.31},
  URN =		{urn:nbn:de:0030-drops-135165},
  doi =		{10.4230/LIPIcs.OPODIS.2020.31},
  annote =	{Keywords: hybrid networks, overlay networks, sparse graphs, cactus graphs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.23
Fast Distributed Algorithms for LP-Type Problems of Low Dimension

Authors: Kristian Hinnenthal, Christian Scheideler, and Martijn Struijs

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this paper we present various distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.
Cite as

Kristian Hinnenthal, Christian Scheideler, and Martijn Struijs. Fast Distributed Algorithms for LP-Type Problems of Low Dimension. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hinnenthal_et_al:LIPIcs.DISC.2019.23,
  author =	{Hinnenthal, Kristian and Scheideler, Christian and Struijs, Martijn},
  title =	{{Fast Distributed Algorithms for LP-Type Problems of Low Dimension}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.23},
  URN =		{urn:nbn:de:0030-drops-113306},
  doi =		{10.4230/LIPIcs.DISC.2019.23},
  annote =	{Keywords: LP-type problems, linear optimization, distributed algorithms, gossip algorithms}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.150
On the Complexity of Local Graph Transformations

Authors: Christian Scheideler and Alexander Setzer

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.
Cite as

Christian Scheideler and Alexander Setzer. On the Complexity of Local Graph Transformations. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 150:1-150:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{scheideler_et_al:LIPIcs.ICALP.2019.150,
  author =	{Scheideler, Christian and Setzer, Alexander},
  title =	{{On the Complexity of Local Graph Transformations}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{150:1--150:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.150},
  URN =		{urn:nbn:de:0030-drops-107266},
  doi =		{10.4230/LIPIcs.ICALP.2019.150},
  annote =	{Keywords: Graphs transformations, NP-hardness, approximation algorithms}
}
Document
DOI: 10.4230/DagRep.8.8.48
Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331)

Authors: Spring Berman, Sándor P. Fekete, Matthew J. Patitz, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 8, Issue 8 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18331,"Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first Dagstuhl seminar on programmable matter (16271), we did focus on some basic problems, but also considered new problems that were now within reach to be studied. During this seminar, we were able to achieve a previously unmatched level of intensity of collaboration, in part due to using a new electronic and interactive web-based platform. This has also allowed for continued research among the attendees based on the work begun during the seminar.
Cite as

Spring Berman, Sándor P. Fekete, Matthew J. Patitz, and Christian Scheideler. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331). In Dagstuhl Reports, Volume 8, Issue 8, pp. 48-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{berman_et_al:DagRep.8.8.48,
  author =	{Berman, Spring and Fekete, S\'{a}ndor P. and Patitz, Matthew J. and Scheideler, Christian},
  title =	{{ Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331)}},
  pages =	{48--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{8},
  editor =	{Berman, Spring and Fekete, S\'{a}ndor P. and Patitz, Matthew J. and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.8.48},
  URN =		{urn:nbn:de:0030-drops-102352},
  doi =		{10.4230/DagRep.8.8.48},
  annote =	{Keywords: computational geometry, distributed algorithms, DNA computing, programmable matter, swarm robotics}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.52
Shape Recognition by a Finite Automaton Robot

Authors: Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).
Cite as

Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, and Christian Scheideler. Shape Recognition by a Finite Automaton Robot. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gmyr_et_al:LIPIcs.MFCS.2018.52,
  author =	{Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian},
  title =	{{Shape Recognition by a Finite Automaton Robot}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.52},
  URN =		{urn:nbn:de:0030-drops-96347},
  doi =		{10.4230/LIPIcs.MFCS.2018.52},
  annote =	{Keywords: finite automata, shape recognition, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.137
Distributed Monitoring of Network Properties: The Power of Hybrid Networks

Authors: Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.
Cite as

Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 137:1-137:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gmyr_et_al:LIPIcs.ICALP.2017.137,
  author =	{Gmyr, Robert and Hinnenthal, Kristian and Scheideler, Christian and Sohler, Christian},
  title =	{{Distributed Monitoring of Network Properties: The Power of Hybrid Networks}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{137:1--137:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.137},
  URN =		{urn:nbn:de:0030-drops-73750},
  doi =		{10.4230/LIPIcs.ICALP.2017.137},
  annote =	{Keywords: Network Monitoring, Hybrid Networks, Overlay Networks}
}
Document
DOI: 10.4230/DagRep.6.7.1
Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)

Authors: Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 6, Issue 7 (2016)

Abstract
his report documents the program and the outcomes of Dagstuhl Seminar 16271 "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of the Dagstuhl seminar was to bring together researchers from the algorithms community with selected experts from robotics and distributed systems in order to set a solid base for the development of models, technical solutions, and algorithms that can control programmable matter. Both communities benefited from such a meeting for the following reasons: - Meeting experts from other fields provided additional insights, challenges and focus when considering work on programmable matter. - Interacting with colleagues in a close and social manner gave many starting points for continuing collaboration. - Getting together in a strong, large and enthusiastic group provided the opportunity to plan a number of followup activities. In the following, we provide details and activities of this successful week.
Cite as

Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271). In Dagstuhl Reports, Volume 6, Issue 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{fekete_et_al:DagRep.6.7.1,
  author =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{7},
  editor =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.7.1},
  URN =		{urn:nbn:de:0030-drops-67599},
  doi =		{10.4230/DagRep.6.7.1},
  annote =	{Keywords: distributed algorithms, distributed systems, programmable matter, robotics, self-organization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.24
Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures

Authors: Christian Scheideler, Alexander Setzer, and Thim Strothmann

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et al. (SSS 2014). This makes our protocol even capable of handling node dynamics.
Cite as

Christian Scheideler, Alexander Setzer, and Thim Strothmann. Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{scheideler_et_al:LIPIcs.OPODIS.2015.24,
  author =	{Scheideler, Christian and Setzer, Alexander and Strothmann, Thim},
  title =	{{Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.24},
  URN =		{urn:nbn:de:0030-drops-66135},
  doi =		{10.4230/LIPIcs.OPODIS.2015.24},
  annote =	{Keywords: Topological Self-Stabilization, Monotonic Searchability, Node Departures}
}
Document
DOI: 10.4230/DagRep.4.1.152
Algorithms for Wireless Communication (Dagstuhl Seminar 14051)

Authors: Guy Even, Magnus Halldorson, Yvonne Anne Pignolet, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 4, Issue 1 (2014)

Abstract
This report documents the talks and discussions of Dagstuhl Seminar 14051 "Algorithms for Wireless Communication". The presented talks represent a wide spectrum of work on wireless networks. The topic of wireless communication continues to grow in many domains, new applications and deployments of wireless networks in a variety of contexts are being reported. A key focus of the talks and discussions presented here is to discuss models for wireless networks as well as algorithmic results and real world deployments.
Cite as

Guy Even, Magnus Halldorson, Yvonne Anne Pignolet, and Christian Scheideler. Algorithms for Wireless Communication (Dagstuhl Seminar 14051). In Dagstuhl Reports, Volume 4, Issue 1, pp. 152-169, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{even_et_al:DagRep.4.1.152,
  author =	{Even, Guy and Halldorson, Magnus and Pignolet, Yvonne Anne and Scheideler, Christian},
  title =	{{Algorithms for Wireless Communication (Dagstuhl Seminar 14051)}},
  pages =	{152--169},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{1},
  editor =	{Even, Guy and Halldorson, Magnus and Pignolet, Yvonne Anne and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.1.152},
  URN =		{urn:nbn:de:0030-drops-45397},
  doi =		{10.4230/DagRep.4.1.152},
  annote =	{Keywords: wireless, algorithms, model, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.129
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing

Authors: Petr Kolman and Christian Scheideler

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
An elementary h-route flow, for an integer h >= 1, is a set of h edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an h-route flow is a non-negative linear combination of elementary h-route flows. An h-route cut is a set of edges whose removal decreases the maximum h-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of this paper is an approximate duality theorem for multicommodity $h$-route cuts and flows, for h <= 3: The size of a minimum h-route cut is at least f/h and at most O(log^3(k)f) where f is the size of the maximum h-route flow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problem for h=3 that has an approximation ratio of O(log^3 k). Previously, polylogarithmic approximation was known only for $h$-route cuts for h <= 2. A key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity flows and cuts. Similar results are shown also for the sparsest multiroute cut problem.
Cite as

Petr Kolman and Christian Scheideler. Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 129-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kolman_et_al:LIPIcs.STACS.2011.129,
  author =	{Kolman, Petr and Scheideler, Christian},
  title =	{{Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{129--140},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.129},
  URN =		{urn:nbn:de:0030-drops-30051},
  doi =		{10.4230/LIPIcs.STACS.2011.129},
  annote =	{Keywords: Multicommodity flow, Multiroute flow, Cuts, Duality}
}
Document
DOI: 10.4230/DagSemProc.09371.6
Stabilizing Consensus with the Power of Two Choices

Authors: Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
Consensus problems occur in many contexts and have therefore been intensively studied in the past. In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Coming up with a self-stabilizing rule is easy without adversarial involvement, but we allow some T-bounded adversary to manipulate any T processes at any time. In this situation, a perfect consensus is impossible to reach, so we only require that there is a time point t and value v so that at any point after t, all but up to O(T) processes agree on v, which we call an almost stable consensus. As we will demonstrate, there is a surprisingly simple rule for the standard message passing model that just needs O(log n loglog n) time for any sqrt{n}-bounded adversary and just O(log n) time without adversarial involvement, with high probability, to reach an (almost) stable consensus from any initial state. A stable consensus is reached, with high probability, in the absence of adversarial involvement.
Cite as

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing Consensus with the Power of Two Choices. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:DagSemProc.09371.6,
  author =	{Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian},
  title =	{{Stabilizing Consensus with the Power of Two Choices}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.6},
  URN =		{urn:nbn:de:0030-drops-24290},
  doi =		{10.4230/DagSemProc.09371.6},
  annote =	{Keywords: Distributed consensus}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact